package com.fengye.algorithms.leecode;

import java.util.*;

/**
 * @Author fengye
 * @Date 2023/4/8 10:38
 **/
public class PermuteUnique47 {

    public static void main(String[] args) {
        new PermuteUnique47().permuteUnique(new int[]{1,1,2}).stream().forEach(System.out::println);
    }



    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        boolean[] vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, vis,0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, boolean[] vis, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, vis,idx + 1, perm);
            // 回溯
            vis[i] = false;
            perm.remove(idx);
        }
    }

    public List<List<Integer>> permuteUnique1(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums.length == 0) {
            return result;
        }
        if(nums.length == 1) {
            List<Integer> temp = new ArrayList<>();
            temp.add(nums[0]);
            result.add(temp);
            return result;
        }
        Set<List<Integer>> resultSet = new HashSet<>();
        doOrder(resultSet, nums, nums.length);
        return new ArrayList<>(resultSet);
    }

    public void doOrder(Set<List<Integer>> resultSet, int[] nums, int size) {
        if(size <= 1){
            return;
        }

        for (int i = 0; i < size;i++) {
            doOrder(resultSet, nums, size-1);
            if(size == 2) {
                List<Integer> temp = new ArrayList<>();
                for (int j = 0; j < nums.length;j++) {
                    temp.add(nums[j]);
                }
                resultSet.add(temp);
            }
            rotate(nums, size);
        }
    }

    public static void rotate(int[] nums, int size) {
        int pos = nums.length - size;
        int temp = nums[pos];
        int i=0;
        for(i=pos+1;i<nums.length;i++) {
            nums[i-1] = nums[i];
        }
        nums[i-1] = temp;
    }
}
